package day2;

/**
 * 
 * 堆排序：
 * 首先使用二分法，将数组分成两侧，接着分别让两侧有序
 * 然后在进行对比两侧数据，进行合并。
 * 该算法的耗时可以使用master公式进行计算
 * T(N)=a*T(N/b)+T(N^d)
 */
public class MergeSort {
    public static void mergeSort(int[] array){
        //判断数组状况
        if (array==null||array.length<2) {
            return ;
        }

        //开始推排序
        process(array,0,array.length-1);
    }

    private static void process(int[] array,int leftIndex,int rightIndex) {
        if (leftIndex==rightIndex) {
            return;
        }
        //防止越界
        int mid=leftIndex+((rightIndex-leftIndex)>>1);
        //令左侧有序
        process(array, leftIndex, mid);
        //令右侧有序
        process(array, mid+1, rightIndex);
        //合并两侧有序至整体有序
        merge(array,leftIndex,mid,rightIndex);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        //临时中间数组
        int[] temp=new int[right-left+1];
        //中间数组索引
        int tempIndex=0;
        //左侧数组索引
        int leftIndex=left;
        //右侧数组索引
        int rightIndex=mid+1;

        //两侧数组都没越界，则谁小将谁移动到中间数组
        while (leftIndex<=mid&&rightIndex<=right) {
            temp[tempIndex++]=array[leftIndex]<=array[rightIndex]?array[leftIndex++]:array[rightIndex++];
        }

        //第一个while不满足那么下面两个循环必只能满足一个
        while (leftIndex<=mid) {
            temp[tempIndex++]=array[leftIndex++];
        }

        while (rightIndex<=right) {
            temp[tempIndex++]=array[rightIndex++];
        }

        //最后将中间
        for (int i = 0; i < temp.length; i++) {
            //需要注意数组下标
            array[left+i]=temp[i];
        }

    }

    public static void main(String[] args) {
        int[] array=new int[]{1,3,5,43,2,32,45,21,246,7,3};
        mergeSort(array);
        for (int num : array) {
            System.out.print(num+" ");
        }
    }
}
